package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/3 17:04
 */
public class J60 {

    /** https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/ */
    /**
     * 暴力解 找规律：s共有 6^n种情况，共有5*n+1种不重复结果
     */
    public static double[] dicesProbability(int n) {
        //思路一：遍历 5*n+1种不重复结果，计算每一种不重复结果的组合个数
        double[] res = new double[5 * n + 1];
        int curSum = n;
        for (int i = 0; i < res.length; ++i) {
            res[i] = countSum(curSum, n) / Math.pow(6, n);
            ++curSum;
        }
        return res;
    }

    static int countSum(int curSum, int n) {
        if (n < 0 || curSum < 0) {
            return 0;
        }
        if (n == 0 && curSum == 0) {
            return 1;
        }
        int sum = 0;
        for (int i = 1; i < 7; ++i) {
            sum += countSum(curSum - i, n - 1);
        }
        return sum;
    }

    public static double[] dp(int n) {
        int[][] dp = new int[n][6 * n];
        for (int j = 0; j < 6; ++j) {
            dp[0][j] = 1;
        } //初始状态

        for (int i = 1; i < n; ++i) { //处理行
            for (int j = i; j < (i + 1) * 6; ++j) {
                for (int dice = 1; dice < 7; ++dice) {
                    if (j - dice < 0) {
                        break;
                    }
                    dp[i][j] += dp[i - 1][j - dice];
                }
            }
        }
        double[] res = new double[5 * n + 1];
        int j = n - 1;
        for (int i = 0; i < res.length; ++i) {
            res[i] = dp[n - 1][j++] / Math.pow(6, n);
        }
        return res;
    }


    // for test
    public static void main(String[] args) {
        int n = 2;
        double[] ans = dicesProbability(n);
        double[] ans2 = dp(n);
        System.out.println(Arrays.toString(ans));
        System.out.println(Arrays.toString(ans2));
    }


}
